//
// Created by francklinson on 2021/5/25.
//

#include <iostream>
#include <vector>

using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode *convertBiNode(TreeNode *root) {
        if (root == nullptr) return nullptr;
        // 通过中序遍历把所有节点放到vector中，再形成链表
        vector<TreeNode *> v;
        dfs(root, v);
        // 将v中的节点形成链表
        for (int i = 0; i < v.size() - 1; ++i) {
            v[i]->left = nullptr;
            v[i]->right = v[i + 1];
        }
        v.back()->left = nullptr;
        v.back()->right = nullptr;
        return v.front();
    }

    void dfs(TreeNode *root, vector<TreeNode *> &v) {
        if (root == nullptr) return;
        dfs(root->left, v);
        v.push_back(root);
        dfs(root->right, v);
    }
};

class Solution2 { // 纯递归
public:
    TreeNode *first = nullptr;   //first指向链表第一个结点
    void fun(TreeNode *root, TreeNode *&pre) {         //root为当前结点，pre指向root的前一个结点
        if (root == nullptr)return;
        fun(root->left, pre);

        if (pre == nullptr) {     //最开始的时候
            pre = root;
            first = root;
        } else {                    //中间结点
            pre->right = root;
            root->left = nullptr;
            pre = root;
        }

        fun(root->right, pre);
    }

    TreeNode *convertBiNode(TreeNode *root) {
        TreeNode *pre = nullptr;
        fun(root, pre);
        return first;       //返回链表头指针
    }
};


int main() {
    auto n1 = TreeNode(4), n2 = TreeNode(2), n3 = TreeNode(5), n4 = TreeNode(1),
            n5 = TreeNode(3), n6 = TreeNode(6), n7 = TreeNode(0);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n3.right = &n6;
    n4.left = &n7;
    Solution2 sol;
    sol.convertBiNode(&n1);
    return 0;
}